Field of the Disclosure
This disclosure relates generally to concurrent programming, and more particularly to systems and methods for enhancing progress for hardware transactional memory.
Description of the Related Art
Traditionally, hardware transactional memory (HTM) supports a model of concurrent programming where the programmer specifies which code blocks should be atomic, but not how that atomicity is achieved. Transactional programming models may provide simpler code structure and better concurrency compared to traditional lock-based synchronization.
Transactional Memory™ is a concurrency control technology that enables parallel programs to perform correct data sharing between concurrent computations (e.g., “threads”). Using transactional memory, programmers may specify what should be done atomically, rather than how this atomicity should be achieved. The transactional memory implementation may then be responsible for guaranteeing the atomicity, largely relieving programmers of the complexity, tradeoffs, and software engineering problems typically associated with concurrent programming and execution. Transactional memory is generally implemented either as hardware transactional memory (HTM) or as software transactional memory (STM). HTM may directly ensure that a transaction is atomic, whereas (STM) may provide an illusion that a transaction is atomic, even though in fact it may actually be executed in smaller atomic steps by underlying hardware. HTM solutions are generally faster than STM ones, but so-called “best-effort” HTM implementations may not guarantee the ability to commit any particular transaction.
An atomic code block may be called a transaction and HTM may execute such transactions speculatively. For example, with HTM, if an attempt to execute a transaction commits, that atomic code block appears to have executed instantaneously and in its entirety. However, if the transaction aborts (e.g., fails to commit) that atomic code block has no effect, and control generally passes to an abort handler. A condition code may be used to indicate why the transaction failed (to commit).
One limitation of traditional HTM systems may be that, with some exceptions, they are best-effort implementations. In other words, HTM implementations typically make no guarantee that any transaction, however small or simple, will ever commit. As a result, it is usually necessary to provide two code paths: a fast, speculative transactional path to be taken in the common case, and a slower, non-speculative (e.g., lock-based) path, to be taken if the fast path repeatedly fails. Moreover, taking the non-speculative path frequently aborts any concurrent speculative transactions, even if there is no actual data conflict between the speculative and non-speculative threads. The reduced concurrency stemming from the need to provide two code paths may be considered to somewhat dilute the advantages of HTM.
An alternative way to guarantee progress may involve allowing a thread that is not making progress to suspend the other threads and run by itself. Under a transactional lock removal approach, conflicts may be resolved using timestamps, and progress is ensured by rolling back and suspending all but the transaction with the oldest timestamp. Similar “serial-mode” techniques have been proposed for transactional memory in high-end embedded systems. However, allowing transactions to force the system into serial mode can severely restrict concurrency, and may also provide a possible denial-of-service vector.